Search for: All records

Effective file system testing relies on coverage to detect bugs and enhance reliability. We analyzed real file system bugs and found a weak correlation between code coverage, the most commonly used metric, and test effectiveness; many bugs were in covered code but remained undetected. Our study also showed that covering diverse file system inputs and outputs—system call arguments and return values—can be key to detecting the majority of observed bugs. We present input coverage and output coverage as new metrics for evaluating and improving file system testing, and have developed the IOCov framework for computing these metrics. Unlike existing system call tracers, IOCov computes coverage using only the calls relevant to testing, excluding unrelated ones that should not be counted. To demonstrate IOCov’s utility, we used it to extend the existing testing tool CrashMonkey into CM-IOCov, which achieves broader input coverage and more thorough detection of crash consistency bugs. Our experimental evaluation shows that IOCov com- putes input and output coverage accurately with minimal overhead. IOCov is applicable to different types of file system testing and can provide insights for improvement as well as identify untested cases based on coverage results. Moreover, the bugs found exclusively by CM-IOCov are 2.1 and 12.9 times more than those found exclusively by CrashMonkey on the 6.12 and 5.6 kernels, respectively, demonstrating the effectiveness of the IOCov-based coverage approach. 

Identifying knee and elbow points in performance curves is a critical task in various domains, including machine learning and system design. These points represent optimal trade-offs between cost and performance, facilitating efficient decision-making and resource allocation. However, accurately determining the knees and elbows in curves poses a significant challenge. To address this challenge, we introduce Kneeliverse, an open-source library dedicated to knee/elbow point detection. Kneeliverse incorporates a suite of well-established knee-detection algorithms, including Menger, L-method, Kneedle, and DFDT. Additionally, Kneeliverse extends these algorithms to detect multiple knees and elbows in complex curves, employing a recursive approach. Kneeliverse further includes Z-Method, a recently developed algorithm specifically designed for multi-knee detection. 

Abstract BackgroundInteraction analysis via movement in space and time contributes to understanding social relationships among individuals and their dynamics in ecological systems. While there is an exciting growth in research in computational methods for interaction analysis using movement data, there remain challenges regarding reproducibility and replicability of the existing approaches. The current movement interaction analysis tools are often less accessible or tested for broader use in ecological research. To address these challenges, this paper presents ORTEGA, an Object-oRiented TimE-Geographic Analytical tool, as an open-source Python package for analyzing potential interactions between pairs of moving entities based on the observation of their movement. ORTEGA is developed based on one of the newly emerged time-geographic approaches for quantifying space-time interaction patterns among animals. A case study is presented to demonstrate and evaluate the functionalities of ORTEGA in tracing dynamic interaction patterns in animal movement data. Besides making the analytical code and data freely available to the community, the developed package also offers an extension of the existing theoretical development of ORTEGA for incorporating a context-aware ability to inform interaction analysis. ORTEGA contributes two significant capabilities: (1) the functions to identify potential interactions (e.g., encounters, concurrent interactions, delayed interactions) from movement data of two or more entities using a time-geographic-based approach; and (2) the capacity to compute attributes of potential interaction events including start time, end time, interaction duration, and difference in movement parameters such as speed and moving direction, and also contextualize the identified potential interaction events. 

Abstract BackgroundInteraction through movement can be used as a marker to understand and model interspecific and intraspecific species dynamics, and the collective behavior of animals sharing the same space. This research leverages the time-geography framework, commonly used in human movement research, to explore the dynamic patterns of interaction between Indochinese tigers (Panthera tigris corbeti) in the western forest complex (WEFCOM) in Thailand. MethodsWe propose and assess ORTEGA, a time-geographic interaction analysis method, to trace spatio-temporal interactions patterns and home range shifts among tigers. Using unique GPS tracking data of tigers in WEFCOM collected over multiple years, concurrent and delayed interaction patterns of tigers are investigated. The outcomes are compared for intraspecific tiger interaction across different genders, relationships, and life stages. Additionally, the performance of ORTEGA is compared to a commonly used proximity-based approach. ResultsAmong the 67 tracked tigers, 42 show concurrent interactions at shared boundaries. Further investigation of five tigers with overlapping home ranges (two adult females, a male, and two young male tigers) suggests that the mother tiger and her two young mostly stay together before their dispersal but interact less post-dispersal. The male tiger increases encounters with the mother tiger while her young shift their home ranges. On another timeline, the neighbor female tiger mostly avoids the mother tiger. Through these home range dynamics and interaction patterns, we identify four types of interaction among these tigers: following, encounter, latency, and avoidance. Compared to the proximity-based approach, ORTEGA demonstrates better detects concurrent mother–young interactions during pre-dispersal, while the proximity-based approach misses many interactions among the dyads. With larger spatial buffers and temporal windows, the proximity-based approach detects more encounters but may overestimate the duration of interaction. ConclusionsThis research demonstrates the applicability and merits of ORTEGA as a time-geographic based approach to animal movement interaction analysis. We show time geography can develop valuable, data-driven insights about animal behavior and interactions. ORTEGA effectively traces frequent encounters and temporally delayed interactions between animals, without relying on specific spatial and temporal buffers. Future research should integrate contextual and behavioral information to better identify and characterize the nature of species interaction. 

This paper introduces a novel Perturbation-Assisted Inference (PAI) framework utilizing synthetic data generated by the Perturbation-Assisted Sample Synthesis (PASS) method. The framework focuses on uncertainty quantification in complex data scenarios, particularly involving unstructured data while utilizing deep learning models. On one hand, PASS employs a generative model to create synthetic data that closely mirrors raw data while preserving its rank properties through data perturbation, thereby enhancing data diversity and bolstering privacy. By incorporating knowledge transfer from large pretrained generative models, PASS enhances estimation accuracy, yielding refined distributional estimates of various statistics via Monte Carlo experiments. On the other hand, PAI boasts its statistically guaranteed validity. In pivotal inference, it enables precise conclusions even without prior knowledge of the pivotal’s distribution. In non-pivotal situations, we enhance the reliability of synthetic data generation by training it with an independent holdout sample. We demonstrate the effectiveness of PAI in advancing uncertainty quantification in complex, data-driven tasks by applying it to diverse areas such as image synthesis, sentiment word analysis, multimodal inference, and the construction of prediction intervals. 

Storage cache hierarchies include diverse topologies, assorted parameters and policies, and devices with varied performance characteristics. Simulation enables efficient exploration of their configuration space while avoiding expensive physical experiments. Miss Ratio Curves (MRCs) efficiently characterize the performance of a cache over a range of cache sizes, revealing ‘‘key points’’ for cache simulation, such as knees in the curve that immediately follow sharp cliffs. Unfortunately, there are no automated techniques for efficiently finding key points in MRCs, and the cross-application of existing knee-detection algorithms yields inaccurate results. We present a multi-stage framework that identifies key points in any MRC, for both stack- based (e.g., LRU) and more sophisticated eviction algorithms (e.g., ARC). Our approach quickly locates candidates using efficient hash-based sampling, curve simplification, knee detection, and novel post-processing filters. We introduce Z-Method, a new multi-knee detection algorithm that employs statistical outlier detection to choose promising points robustly and efficiently. We evaluated our framework against seven other knee-detection algorithms, identifying key points in multi-tier MRCs with both ARC and LRU policies for 106 diverse real-world workloads. Compared to naïve approaches, our framework reduced the total number of points needed to accurately identify the best two-tier cache hierarchies by an average factor of approximately 5.5x for ARC and 7.7x for LRU. We also show how our framework can be used to seed the initial population for evolutionary algorithms. We ran 32,616 experiments requiring over three million cache simulations, on 151 samples, from three datasets, using a diverse set of population initialization techniques, evolutionary algorithms, knee-detection algorithms, cache replacement algorithms, and stopping criteria. Our results showed an overall acceleration rate of 34% across all configurations. 

We present Metis, a model-checking framework designed for versatile, thorough, yet configurable file system testing in the form of input and state exploration. It uses a nondeterministic loop and a weighting scheme to decide which system calls and their arguments to execute. Metis features a new abstract state representation for file-system states in support of efficient and effective state exploration. While exploring states, it compares the behavior of a file system under test against a reference file system and reports any discrepancies; it also provides support to investigate and reproduce any that are found. We also developed RefFS, a small, fast file system that serves as a reference, with special features designed to accelerate model checking and enhance bug reproducibility. Experimental results show that Metis can flexibly generate test inputs; also the rate at which it explores file-system states scales nearly linearly across multiple nodes. RefFS explores states 3–28x faster than other, more mature file systems. Metis aided the development of RefFS, reporting 11 bugs that we subsequently fixed. Metis further identified 12 bugs from five other file systems, five of which were confirmed and with one fixed and integrated into Linux. 

We present Metis, a model-checking framework designed for versatile, thorough, yet configurable file system testing in the form of input and state exploration. It uses a nondeterministic loop and a weighting scheme to decide which system calls and their arguments to execute. Metis features a new abstract state representation for file-system states in support of efficient and effective state exploration. While exploring states, it compares the behavior of a file system under test against a reference file system and reports any discrepancies; it also provides support to investigate and reproduce any that are found. We also developed RefFS, a small, fast file system that serves as a reference, with special features designed to accelerate model checking and enhance bug reproducibility. Experimental results show that Metis can flexibly generate test inputs; also the rate at which it explores file-system states scales nearly linearly across multiple nodes. RefFS explores states 3–28× faster than other, more mature file systems. Metis aided the development of RefFS, reporting 11 bugs that we subsequently fixed. Metis further identified 12 bugs from five other file systems, five of which were confirmed and with one fixed and integrated into Linux. 

Abstract Understanding interactions through movement provides critical insights into urban dynamic, social networks, and wildlife behaviors. With widespread tracking of humans, vehicles, and animals, there is an abundance of large and high‐resolution movement data sets. However, there is a gap in efficient GIS tools for analyzing and contextualizing movement patterns using large movement datasets. In particular, tracing space–time interactions among a group of moving individuals is a computationally demanding task, which would uncover insights into collective behaviors across systems. This article develops a Spark‐based geo‐computational framework through the integration of Esri's ArcGIS GeoAnalytics Engine and Python to optimize the computation of time geography for scaling up movement interaction analysis. The computational framework is then tested using a case study on migratory turkey vultures with over 2 million GPS tracking points across 20 years. The outcomes indicate a drastic reduction in interaction detection time from 14 days to 6 hours, demonstrating a remarkable increase in computational efficiency. This work contributes to advancing GIS computational capabilities in movement analysis, highlighting the potential of GeoAnalytics Engine in processing large spatiotemporal datasets.